# 给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。
#  字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。
#
#  示例 1：
#  输入：s1 = "abc", s2 = "xya"
# 输出：true
# 解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
#
#  示例 2：
#  输入：s1 = "abe", s2 = "acd"
# 输出：false
# 解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括：
# "acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。
#
#  示例 3：
#  输入：s1 = "leetcodee", s2 = "interview"
# 输出：true
class Solution:
    def checkIfCanBreak2(self, s1: str, s2: str) -> bool:
        """
        比较累积字母频数曲线
        :param s1:
        :param s2:
        :return:
        """
        from itertools import accumulate
        from collections import Counter
        c1, c2 = Counter(s1), Counter(s2)  # 统计每个字母出现的次数
        chars = [chr(97 + i) for i in range(26)]
        acc1 = list(accumulate(c1[char] for char in chars))  # 从 a-z 累计每个字母出现的次数
        acc2 = list(accumulate(c2[char] for char in chars))
        return all(a1 <= a2 for a1, a2 in zip(acc1, acc2)) or all(a1 >= a2 for a1, a2 in zip(acc1, acc2))

    def checkIfCanBreak1(self, s1: str, s2: str) -> bool:
        """
        排序 + 贪心
        先将s1,s2按照字典序排好，然后逐位位判断能否"打破"
        :param s1:
        :param s2:
        :return:
        """
        # lst1, lst2 = sorted(s1), sorted(s2)
        # i = 0
        # n = len(lst1)
        # while i < n:  # 首先找到排序后s1 s2不相等的首个位置
        #     if lst1[i] != lst2[i]:
        #         break
        #     i += 1
        # # 后面的逐位尝试是否能打破
        # if lst1[i] < lst2[i]:
        #     while i < n:
        #         if lst1[i] > lst2[i]:
        #             return False
        #         i += 1
        # else:
        #     while i < n:
        #         if lst1[i] < lst2[i]:
        #             return False
        #         i += 1
        # return True

        # 写法二
        lst1, lst2 = sorted(s1), sorted(s2)
        # print((c1 <= c2 for c1, c2 in zip(lst1, lst2)))  # 生成器对象(外围括号可省)
        # print([c1 <= c2 for c1, c2 in zip(lst1, lst2)])  # list
        return all(c1 <= c2 for c1, c2 in zip(lst1, lst2)) or all(c1 >= c2 for c1, c2 in zip(lst1, lst2))

    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        return self.checkIfCanBreak2(s1, s2)


if __name__ == '__main__':
    s1 = "abc"
    s2 = "xya"
    s1 = "leetcodee"
    s2 = "interview"
    # s1 = "abe"
    # s2 = "acd"
    print(Solution().checkIfCanBreak(s1, s2))
